/**
?* Note: The returned array must be malloced, assume caller calls free().
?*/

int* copydata(int* nums, int numsSize){
? ? int* ret = (int*)malloc(sizeof(int) * numsSize);
? ? if (ret == NULL) {
? ? ? ? return NULL;
? ? }
? ? memcpy(ret, nums, sizeof(int) * numsSize);
? ? return ret;
}

int compare(const void* a, const void* b) {
? ? int x = *(int*) a;
? ? int y = *(int*) b;
? ? return x - y;
}

void findPosition(int* nums, int numsSize, int num1, int num2, int* res)
{
? ? for (int i = 0; i < numsSize; i++) {
? ? ? ? if (nums[i] == num1) {
? ? ? ? ? ? res[0] = i;
? ? ? ? ? ? break;
? ? ? ? }
? ? }

? ? for (int i = 0; i < numsSize; i++) {
? ? ? ? if (nums[i] == num2 && i != res[0]) {
? ? ? ? ? ? res[1] = i;
? ? ? ? ? ? break;
? ? ? ? }
? ? }

}

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
? ? int* res = (int*)malloc(sizeof(int) * 2);
? ? if (res == NULL) {
? ? ? ? return NULL;
? ? }

? ? int* arr = copydata(nums, numsSize);
? ? qsort(arr, numsSize, sizeof(int), compare);

? ? *returnSize = 2;
? ? int left, right, sum;
? ? left = 0;
? ? right = numsSize - 1;
? ? while (left < right) {
? ? ? ? sum = arr[left] + arr[right];
? ? ? ? if (sum == target) {
? ? ? ? ? ? findPosition(nums, numsSize, arr[left], arr[right], res);
? ? ? ? ? ? return res;
? ? ? ? }

? ? ? ? if (sum > target) {
? ? ? ? ? ? right--;
? ? ? ? } else {
? ? ? ? ? ? left++;
? ? ? ? }
? ? }

? ? return NULL;
}
